package leetcode_201_300;

public class LeeCode_221 {
    public static void main(String[] args) {
//        System.out.println(maximalSquare(new char[][]{{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'},
//                {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}}));
//        System.out.println(maximalSquare(new char[][]{
//                {'0','0','0','1'},
//                {'1','1','0','1'},
//                {'1','1','1','1'},
//                {'0','1','1','1'},
//                {'0','1','1','1'},
//        }));
        System.out.println(maximalSquare2(new char[][]{
                {'0','0','0','1'},
                {'1','1','1','1'},
                {'1','1','1','0'},
                {'0','1','1','1'},
                {'0','1','1','1'},
        }));

    }
    private static int maximalSquare2(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int max = 0;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    dp[i + 1][j + 1] = Math.min(Math.min(dp[i][j + 1], dp[i][j]), dp[i + 1][j]) + 1;
                    max = Math.max(max, dp[i + 1][j + 1]);
                }
            }
        }
        return max * max;
    }
    private static int maximalSquare(char[][] matrix) {
        int[] max = new int[1];
        int m = matrix.length;
        int n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1'){
                    max[0] = Math.max(max[0], 1);
                    dfs(matrix, i, j, 1, max);
                }
            }
        }
        return max[0];
    }
    private static void dfs(char[][] matrix, int oldI, int oldJ, int side, int[] max){
        int ds_i = oldI, ds_j = oldJ + side, rs_i = oldI + side, rs_j = oldJ;
        if (ds_j >= matrix[0].length || rs_i >= matrix.length)
            return;
        boolean flag = true;
        while (true){
            if (ds_i == rs_i && ds_j == rs_j){
                if (matrix[ds_i][ds_j] == '0') {
                    flag = false;
                }
                break;
            }
            if (matrix[ds_i][ds_j] == '0') {
                flag = false;
            }
            ds_i++;
            if (matrix[rs_i][rs_j] == '0') {
                flag = false;
            }
            rs_j++;
        }
        if (flag){
            max[0] = Math.max(max[0], (side + 1) * (side + 1));
            dfs(matrix, oldI, oldJ, side + 1, max);
        }
    }
}
